#include <iostream>
#include <cstdlib>

using namespace std;

typedef struct node {
	int id;               // 数据域，保存需要存储的数据 
	 
	struct node *next;    // 指针域，保存下一个节点的地址 
}Node; 

Node* SList_Creat() {
    int data;              // 表示数据域的数据	
    Node* head = NULL;     // 指向头节点的指针
	
    // 创建头节点
    head = (Node*)malloc(sizeof(Node));
    if(NULL == head) {
        perror("malloc: ");
        return NULL;
    }
	
    // 马上给头节点赋值
    // 头节点中，并不会存储有效数据 
    head -> id = -1;        // 此例中，-1 是停止创建链表的信号，故不是有效数据
    head -> next = NULL;    // 目前为止，内存中只有一个节点，故头节点指针域为空
	
    // 循环创建新节点之前，需要两个辅助指针
    Node* pCur = head;   // 始终表示当前节点，且当前只有头节点一个节点
    Node* pNew = NULL;   // 始终表示新创建的节点，且当前还未创建节点
	
    // 开始循环创建节点
    while(1) {
        cout << "请输入数据: ";
        cin >> data; 
		
        if(-1 == data) {
            break;
        }
		
        // 开始创建新的节点
        pNew = (Node*)malloc(sizeof(Node)); 
        if(NULL == pNew) {
            perror("malloc: ");
            return NULL;
        }
		
        // 给新创建的节点赋值
        pNew -> id = data; 
        pNew -> next = NULL;
		
        // 建立节点之间的联系
        pCur -> next = pNew;
        pCur = pNew;
		
        pNew = NULL;
    } 
	
    return head;   // 返回链表中头节点的地址
}

int SList_Print(Node* head) {
    // 判断参数是否合法
    if(NULL == head) {
        return -1; 
    } 
    
    // 头节点中并不会存储有效数据
    // 所以从链表中第一个节点(即头节点的下一个节点)开始遍历
    Node* pCur = head -> next; 
	
    cout << "Head ";
    while(pCur != NULL) {
        cout << " -> " << pCur -> id;
		
        // 重定向指针至: 当前节点的下一个节点 
        pCur = pCur -> next;    
    } 
    cout << " -> NULL" << endl;
	
    return 0; 
} 

int SList_Insert(Node* head, int x, int y) {
    if(NULL == head) {
        return -1;
    }
	
    Node* pPre = head;
    Node* pCur = head -> next;
	
    // 寻找 x  节点
    while(pCur != NULL) {
        if(pCur -> id == x) {
            break;
        }
		
        pPre = pCur;
        pCur = pCur -> next;
    }
	
    // 1、链表中有 x 节点，此时 pCur 指向 x，pPre 指向 x 的前驱节点
    // 2、链表中不存在 x ，此时 pCur = NULL, pPre 指向的就是尾节点
    Node* pNew = (Node*)malloc(sizeof(Node)); 
    if(NULL == pNew) {
        return -2;
    }
	
    // 给新节点赋值
    pNew -> id = y; 
    pNew -> next = NULL;
	
    // 执行插入操作
    pPre -> next = pNew;
    pNew -> next = pCur; 
	
    return 0;
} 

int SListNode_Del(Node* head, int x) {
    // 一前一后两个指针，同时从 head 开始扫描链表，当后面那个指针确定了 x 节点之后，
    // 前面那个指针所指向的节点就是 x 的前驱结点
    if(NULL == head) {
        return -1;
    }
	
    Node* pPre = head;
    Node* pCur = head -> next;
	
    // 确定 x 在链表中的位置
    int flag = 0;     // 0 --> 没有 x 节点   1 --> 有 x 节点
    while(pCur != NULL) {
        if(pCur -> id == x) {
            // 执行删除操作 
            // 使 x 的前驱节点，指向 x 的后继节点
            pPre -> next = pCur -> next;
			
            // 记得释放被删除的节点 
            if(pCur != NULL) {
                free(pCur);
                pCur = NULL;
            } 
			
            flag = 1;
            break;      // 仅删除链表中第一个值是 x 的节点 
        }
	    	
        // 如果没找到
        pPre = pCur;
        pCur = pCur -> next; 
    } 
	 
    if(0 == flag) {
        // cout << "链表中不存在值是: " << x << " 的节点" << endl;
        return -2; 
    }
	
    return 0;
} 

int SListNode_Sort(Node* head) {
    if(head == NULL) {
        return -1;
    }
	
    Node* pPre = NULL;
    Node* pCur = NULL;
    Node tmp;
	
    // 开始排序: 头节点不会存储有效数据 
    for(pPre = head -> next; pPre -> next != NULL; pPre = pPre -> next) {
        for(pCur = pPre -> next; pCur != NULL; pCur = pCur -> next) {
			
            // 根据节点中数据域的值，经行升序排序
            if(pPre -> id > pCur -> id) {
                tmp.id = pCur -> id; 
                pCur -> id = pPre -> id;
                pPre -> id = tmp.id;

#if 0				
                // 直接交换两个节点的位置
                tmp = *pCur;
                *pCur = *pPre;
                *pPre = tmp;
				
                // 还要交换指针域的值
                tmp.next = pCur -> next;
                pCur -> next = pPre -> next;
                pPre -> next = tmp.next; 
#endif						 
            } 
        }
    }
	
    return 0;
}

int SListNode_Reverse(Node* head) {
    if(NULL == head) {
        return -1;
    }

    if(NULL == head -> next || NULL == head -> next -> next) {
        return -2;
    }
	
	// 初始状态， pPre 指向链表第一个节点
	// 初始状态， pCur 指向第二个节点 
	Node* pPre = head -> next;
	Node* pCur = pPre -> next;
	
	pPre -> next = NULL;
	Node* tmp = NULL;
	
	while(pCur != NULL) {
		tmp = pCur -> next;
		
		pCur -> next = pPre;
		pPre = pCur;
		pCur = tmp;
	} 
	
	head -> next = pPre;
	
	return 0;
} 

int SListNode_Destroy(Node* head) { 
    if(NULL == head) {
        return -1;
    }
	
    // 指针 tmp 用来保存将被释放节点的后继节点地址 
    Node* tmp = NULL;
    int count = 0;        // 统计释放节点数目

    // 开始挨个释放链表中的节点
    while(head != NULL) {
        // 确保链表不丢失
        tmp = head -> next;  // 把头节点下一个节点的地址，赋值给指针 tmp
		
        // 此时，释放头节点 
        if(head != NULL) {
            free(head);
            head = NULL;   // 防止多次释放 
        }
		
        head = tmp;
        count++;    // 统计一下，总共释放了几个节点 
	} 

    cout << "共释放了: " << count << " 个节点" << endl; 

    return 0;
} 

int main()
{
	// 创建头节点 
	Node* head = SList_Creat();
	
	// 遍历链表
	SList_Print(head);
	
	// 假设链表是: 1 2 3 5 6 7 8 9
	// 把 4 插入到 5 的前面
	cout << "\n链表的插入操作: \n";
	SList_Insert(head, 5, 4);   // 把 4 插入到 5 的前面 
	SList_Print(head);
	SList_Insert(head, 20, 10);  // 因为节点中没有 20，所以 10 会插入到链表末尾 
	SList_Print(head);
	
	cout << "\n链表的删除操作: \n";
	SListNode_Del(head, 8);  // 从链表中，删除值是 8 的节点 
	SList_Print(head);
	SListNode_Del(head, 100);  // 从链表中删除值是 100 的节点，但是没有这个节点 	
	
	cout << "\n链表的排序:\n";
	SListNode_Sort(head);
	SList_Print(head);
	
	cout << "\n销毁链表:\n";
	SListNode_Destroy(head);

	return 0;
}
